package heap;

import java.util.*;

public class HeapOperations {
    //假设是小堆，在满足向下调整的前提下进行调整
    //向下调整的前提：完全二叉树基本已经满足堆的性质，只有要操作的元素位置和其孩子的关系还不明确

    //用递归的方式进行向下调整(小堆)
    public static void adjustDownSmallHeap(long[] array,int size,int index){
        //1.检查要调整的位置[index]是不是一个叶子结点
        //如果是叶子结点，直接结束调整
        int leftIdx = 2 * index + 1;
        if(leftIdx >= size){
            //没有左孩子 -> 叶子结点
            return;
        }
        //2.找到 “我” 这个结点之后的最小的一个孩子
        int minIdx = leftIdx;       //先假设最小的孩子是左孩子
        int rightIdx = leftIdx + 1;
        if(rightIdx < size && array[rightIdx] < array[leftIdx]){
            minIdx = rightIdx;
        }
        //3.比较 “我” 这个结点和最小孩子的值
        if(array[index] <= array[minIdx]){
            return;
        }
        //4.否则，"我" 这个位置不满足堆的性质，进行 “我” 和最小结点的交换
        swap(array,index,minIdx);
        //5.交换结束后，可能新的位置仍然需要进行判断，利用递归进行继续的向下调整
        adjustDownSmallHeap(array,size,minIdx);
    }

    //用非递归的方式进行向下调整(小堆)
    public static void adjustDownSmallHeap1(long[] array,int size,int index){
        while (2 * index + 1 < size){       //判断是不是叶子结点，即有没有左孩子
            //找到最小的孩子
            int minIdx = 2 * index + 1;     //先将左孩子定为最小孩子
            //判断左孩子和右孩子哪一个更小
            if(minIdx + 1 < size && array[minIdx + 1] < array[minIdx]){
                minIdx++;
            }
            //判断 “我” 和最小结点的值的大小关系
            if (array[index] <= array[minIdx]){
                return;
            }
            //“我” 这个结点不小于当前最小结点的值时进行交换
            swap(array,index,minIdx);
            //以最小孩子的位置再一次进行循环
            index = minIdx;
        }
    }

    //用非递归的方式进行大堆的向下调整
    public static void adjustDownBigHeap(long[] array,int size,int index){
        while(2 * index + 1 < size){
            int maxIdx = 2 * index + 1;
            if(maxIdx + 1 < size && array[maxIdx + 1] > array[maxIdx]){
                maxIdx++;
            }
            if(array[index] >= array[maxIdx]){
                return;
            }
            swap(array,index,maxIdx);
            index = maxIdx;
        }
    }
    public static void swap(long[] array,int i,int j){
        long t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    //创建大堆
    public static void creatBigHeap(long[] array,int size){
        //直接求最后一个元素的双亲下标
        //当前结点的下标是 index 时，其左孩子的下标为 2 * index + 1，其右孩子的下标为 2 * index + 2
        //最后一个元素的下标为 size - 1 ，
        //如果这个结点是左孩子，则它的双亲结点的下标为 (size - 1 - 1) / 2,即(size - 2) / 2
        //如果这个结点是右孩子，则它的双亲结点的下标为 (size - 2 - 1) / 2,即(size - 3) / 2
        //直接向下取整，进行计算，为 (size - 2) / 2
        int pIdx = (size - 2) / 2;
        //时间复杂度为：O(n * log(n))
        for (int i = pIdx; i >= 0; i--) {       //依次从下到上进行检查
            adjustDownBigHeap(array,size,i);
        }
    }

    public static void main(String[] args) {
//        long[] array = {10,3,13,2,2,7,8,0,0,0,0};
//        int size = 7;
//        adjustDownBigHeap(array,size,0);
//
//        long[] array = {27,15,19,18,28,34,65,49,25,37};
//        int size = array.length;
//        adjustDownBigHeap(array,size,0);

        long[] array = {9,3,1,7,6,9,2,8,4,0,0,3,6,-1,-1,-1};
        int size = 13;
        creatBigHeap(array,size);
        System.out.println(Arrays.toString(Arrays.copyOf(array,size)));
    }
}
